#include <vector>
#include <unordered_map>
using namespace std;
class Solution1 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();

        vector<int> dp1(size,1),dp2(size,1);

        //预处理前缀积、后缀积数组
        for(int i = 1;i<size;++i)
        dp1[i]=dp1[i-1]*nums[i-1];
        for(int j = size-2;j>=0;--j)
        dp2[j]=dp2[j+1]*nums[j+1];

        //vector<int> answer(size);
        for(int i = 0;i<size;++i)
        {
            nums[i]=dp1[i]*dp2[i];
        }
        return nums;

    }
};

//连续数组
class Solution2 {
public:
    int findMaxLength(vector<int>& nums) {
        for(int& num:nums)
        num = (num == 0) ? -1 : num;
        unordered_map<int,int> hashtable;
        int sum = 0,maxlength = 0;
        for(int i = 0;i<nums.size();++i)
        {
            sum += nums[i];
            if(0 == sum)
            {
            maxlength = std::max(maxlength,i+1);
            continue;
            }
            if(hashtable.count(sum))
            maxlength = std::max(maxlength,i-hashtable[sum]);
            if(!hashtable.count(sum))
            hashtable[sum] = i;
        }
        return maxlength;
    }
};